package com.lun.swordtowardoffer2.c13;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Permute {

	//方法一：交换法
	public List<List<Integer>> permute(int[] nums){
		List<List<Integer>> result = new ArrayList<>();
		backtracking(nums, 0, result);
		return result;
	}
	
	private void backtracking(int[] nums, int startIndex, List<List<Integer>> result) {
		if(nums.length == startIndex) {
			result.add(Arrays.stream(nums).boxed().toList());
		}else {
			for(int i = startIndex; i < nums.length; i++) {
				swap(nums, startIndex, i);
				backtracking(nums, startIndex + 1, result);
				swap(nums, startIndex, i);
			}
		}
	}
	
	private void swap(int[] nums, int i, int j) {
		int temp = nums[i];
		nums[i] = nums[j];
		nums[j] = temp;
	}
	
	//方法二：标记使用法
	public List<List<Integer>> permute2(int[] nums){
		List<List<Integer>> result = new ArrayList<>();
		List<Integer> path = new ArrayList<>();
		boolean[] used = new boolean[nums.length];
		backtracking2(nums, used, path, result);
		return result;
	}

	private void backtracking2(int[] nums, boolean[] used, List<Integer> path, //
								List<List<Integer>> result) {
		if(path.size() == nums.length) {
			result.add(new ArrayList<>(path));
			return;
		}
		
		for(int i = 0; i < nums.length; i++) {
			if(used[i]) continue;
			
			used[i] = true;
			path.add(nums[i]);
			backtracking2(nums, used, path, result);
			path.remove(path.size() - 1);
			used[i] = false;
		}
		
	}
}
